/**
 * 19. 删除链表的倒数第 N 个结点
 */
public class Solution_19 {
    /**
     * 双指针
     * 
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return head;
        }
        // 虚拟头节点
        ListNode dummyHead = new ListNode(0, head);
        // 双指针
        ListNode fast = dummyHead, slow = dummyHead;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummyHead.next;
    }
}
